/*
题目链接：https://leetcode.cn/problems/number-of-digit-one/description/
233. 数字1的个数-困难
完成日期：2024/10/1
数位DP
*/

class Solution {
public:
int dfs(int i, bool limit_low, bool limit_high, int last_one, unordered_map<string, int>& memo,string high,string low) {
        if (i == high.length()) {
            return last_one;
        }
        string key=to_string(i) + "_" + to_string(limit_low) + "_" + to_string(limit_high) + "_" + to_string(last_one);
        if (memo.find(key)!= memo.end()) {
            return memo[key];
        }
        int res = 0;
        int lo = limit_low? low[i] - '0' : 0;
        int hi = limit_high? high[i] - '0' : 9;
        for (int nx = lo; nx <= hi; ++nx) {
            res += dfs(i + 1, limit_low && lo == nx, limit_high && hi == nx, last_one + (nx == 1), memo,high,low);
        }
        memo[key] = res;
        return res;
    }
    int countDigitOne(int n) {
        string high=to_string(n);
        int len = high.length();
        string low(len, '0');
        unordered_map<string, int> memo;
        return dfs(0, true, true, 0, memo,high,low);
    }

    
};